package com.gitee.ywj1352.算法.回溯;

import com.gitee.ywj1352.算法.week02.TreeNode;

public class 将二叉树展开为链表114 {


    // 定义：将以 root 为根的树拉平为链表
    void flatten(TreeNode root) {
        // base case
        if (root == null) return;

        flatten(root.left);
        flatten(root.right);

        /**** 后序遍历位置 ****/
        // 1、左右子树已经被拉平成一条链表
        TreeNode left = root.left;
        TreeNode right = root.right;

        // 2、将左子树作为右子树
        root.left = null;
        root.right = left;

        // 3、将原先的右子树接到当前右子树的末端
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }


    public void f(TreeNode root){
        if (root == null) return;
        f(root.left);
        f(root.right);

        TreeNode leftNode = root.left;
        TreeNode rightNode = root.right;

        root.left = null;
        root.right = leftNode;

        TreeNode p = root;

        while(p.right !=null){
            p = p.right;
        }
        p.right = rightNode;

    }
}
